package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         40,
		Discription: "指定值之和的所有组合(同一个位置的元素不可以重复使用, 不同位置的相同值可以一起使用, 数组中有重复元素,解集不能重复)",
		Level:       2,
		Labels: map[string]int{
			"排序": 1,
			"递归": 1,
			"去重": 1,
		},
	})
}

func CombinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	res := make([][]int, 0)
	comb := make([]int, 0)
	var combine func(int, int)
	combine = func(start, sum int) {
		if sum == target {
			res = append(res, append([]int(nil), comb...))
			return
		}

		for i := start; i < len(candidates); i++ {
            //有重复元素，需要去重
            //comb中每一个位置不能选一样的数，但不同位置可以出现一样的数
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}

			tempSum := sum + candidates[i]
			if tempSum > target {
				break
			}

			comb = append(comb, candidates[i])
			combine(i+1, tempSum)
			comb = comb[:len(comb)-1]
		}
	}

	combine(0, 0)
	return res
}